#include <iostream>
#include <stdlib.h>
#include <math.h>
#include <ctime>

using namespace std;

struct stateNode
{
	unsigned int state;
	stateNode *pPrev;
	stateNode *pNext;
};

stateNode *resQueue;
stateNode *tailResQueue;
stateNode *myQueue;
stateNode *tailQueue;
stateNode *myPath;

int totalSteps = 0;
unsigned int startState;
const unsigned int targetState = 0x29cbb809;//0010 1001 1100 1011 1011 1000 0000 1001;

clock_t begintime;
clock_t finishtime;

void Print01(unsigned int a)
{
	cout<<a<<" is ";
	for(int i=0; i<32; ++i)
	{
		unsigned int tmp = a;
		tmp = tmp>>(31-i);
		tmp = tmp&0x00000001;
		cout << tmp;
	}
	cout<<endl;
}

void PrintArray(unsigned int a)
{
	unsigned int bp = a&0x0000000f;
	unsigned int dgt8[8];
	for(int i=0; i<8; ++i)
	{
		unsigned int tmp = a;
		tmp = tmp>>(32-3*(i+1));
		tmp = tmp&0x00000007;
		if(tmp == 0)
			tmp = 8;
		dgt8[i] = tmp;
//		cout<<dgt8[i]<<" ";
	}
	for(int i=0; i<3; ++i)
	{
		for(int j=0; j<3; ++j)
		{
			if(i*3+j < bp-1)
				cout<<dgt8[i*3+j]<<" ";
			if(i*3+j == bp-1)
				cout<<" "<<" ";
			if(i*3+j > bp-1)
				cout<<dgt8[i*3+j-1]<<" ";
		}
		cout<<endl;
	}
	cout<<"     "<<endl;
}

void Description()
{
//	cout<<"NO INPUT ERROR DETECTION YET ! BE CAREFUL!"<<endl;
	cout<<"SAMPLE INPUT AND OUTPUT FORMAT"<<endl;
	cout<<"input the start state please:1 2 3 4 5 6 7 8"<<endl;
	cout<<"--------------------------------------------"<<endl<<endl;;
//	cout<<"==> 0 steps in total to reach the end state"<<endl;
}

unsigned int array2uint(unsigned int mat[9])
{
	unsigned int pos;
	for(int i=0; i<9; ++i)
		if(mat[i] == 9)
			pos = i+1;

	unsigned int input[8];
	for(int i=0; i<pos-1; ++i)
		input[i] = mat[i];
	for(int i=pos-1; i<8; ++i)
		input[i] = mat[i+1];

	for(int i=0; i<8; ++i)
	{
		input[i] = input[i]&0x00000007;
		input[i] = input[i]<<32-3*(i+1);
	}
	unsigned int ret = (input[0] | input[1] | input[2] | input[3] | input[4] | input[5] | input[6] | input[7] | pos)&0xffffff0f;
	return ret;
}

bool GetInput()
{
	cout<<"input the start state please:";
	unsigned int input[9];
	unsigned int test[8];
	for(int i=0; i<8; ++i)
	{
		cin>>input[i];
		test[i] = input[i];
		input[i] = input[i]&0x00000007;
		input[i] = input[i]<<32-3*(i+1);
	}
	input[8] = 9;

	int sum = 0;

	for(int i=0; i<8; ++i)
		for(int j=0; j<i; ++j)
			if(test[j]>test[i])
				++sum;

	if(sum%2 == 1)
		return false;

	unsigned int blankPos = 9;
	startState = (input[0] | input[1] | input[2] | input[3] | input[4] | input[5] | input[6] | input[7] | blankPos)&0xffffff0f;
	
	myQueue = new stateNode();
	myQueue->state = startState;
	myQueue->pNext = NULL;
	myQueue->pPrev = NULL;
	tailQueue = myQueue;

	resQueue = new stateNode();
	resQueue->state = targetState;
	resQueue->pPrev = NULL;
	resQueue->pNext = NULL;
	tailResQueue = resQueue;

	return true;
}

bool NotInQueue(unsigned int it)
{
	stateNode *cu = myQueue;
	while(cu != NULL)
	{
		if(cu->state == it)
			return false;
		cu = cu->pNext;
	}
	return true;
}

bool NotInResQueue(unsigned int it)
{
	stateNode *cu = resQueue;
	while(cu->pNext!=NULL)
	{
		if(cu->state == it)
			return false;
		cu = cu->pNext;
	}
	if(cu->state == it)
		return false;
	return true;
}

void AddNewNode(stateNode *cu, const unsigned int it)
{
	stateNode *pNode = tailQueue;
	pNode->pNext = new stateNode();
	pNode->pNext->state = it;
	pNode->pNext->pPrev = cu;
	tailQueue = pNode->pNext;
}

void AddNewResNode(stateNode *cu, const unsigned int it)
{
	stateNode *pNode = tailResQueue;
	pNode->pNext = new stateNode();
	pNode->pNext->state = it;
	pNode->pNext->pPrev = cu;
	tailResQueue = pNode->pNext;
}

void AddQueue(stateNode *currState)
{
	unsigned int pos;
	unsigned int dgt9[9];
	unsigned int bp = currState->state&0x0000000f;
	for(int i=0; i<8; ++i)
	{
		unsigned int tmp = currState->state;
		tmp = tmp>>(32-3*(i+1));
		tmp = tmp&0x00000007;
		if(i<bp-1)
			dgt9[i] = tmp;
		else dgt9[i+1] = tmp;
	}
	dgt9[bp-1] = 9;

	//up
	pos = bp-3;
	if((pos>0) && (pos<10))
	{
		unsigned int chg9[9];
		for(int j=0; j<9; ++j) chg9[j] = dgt9[j];
		chg9[bp-1] = chg9[pos-1];
		chg9[pos-1] = 9;
		unsigned int it = array2uint(chg9);

		if(NotInQueue(it))
			AddNewNode(currState, it);
	}
	//down
	pos = bp+3;
	if((pos>0) && (pos<10))
	{
		unsigned int chg9[9];
		for(int j=0; j<9; ++j) chg9[j] = dgt9[j];
		chg9[bp-1] = chg9[pos-1];
		chg9[pos-1] = 9;
		unsigned int it = array2uint(chg9);

		if(NotInQueue(it))
			AddNewNode(currState, it);
	}
	//left
	pos = bp-1;
	if((pos>0) && (pos<10) && ((pos-1)/3 == (bp-1)/3))
	{
		unsigned int chg9[9];
		for(int j=0; j<9; ++j) chg9[j] = dgt9[j];
		chg9[bp-1] = chg9[pos-1];
		chg9[pos-1] = 9;
		unsigned int it = array2uint(chg9);

		if(NotInQueue(it))
			AddNewNode(currState, it);
	}
	//right
	pos = bp+1;
	if((pos>0) && (pos<10) && ((pos-1)/3 == (bp-1)/3))
	{
		unsigned int chg9[9];
		for(int j=0; j<9; ++j) chg9[j] = dgt9[j];
		chg9[bp-1] = chg9[pos-1];
		chg9[pos-1] = 9;
		unsigned int it = array2uint(chg9);

		if(NotInQueue(it))
			AddNewNode(currState, it);
	}
}

void AddResQueue(stateNode *currState)
{
	unsigned int pos;
	unsigned int dgt9[9];
	unsigned int bp = currState->state&0x0000000f;
	for(int i=0; i<8; ++i)
	{
		unsigned int tmp = currState->state;
		tmp = tmp>>(32-3*(i+1));
		tmp = tmp&0x00000007;
		if(i<bp-1)
			dgt9[i] = tmp;
		else dgt9[i+1] = tmp;
	}
	dgt9[bp-1] = 9;

	//up
	pos = bp-3;
	if((pos>0) && (pos<10))
	{
		unsigned int chg9[9];
		for(int j=0; j<9; ++j) chg9[j] = dgt9[j];
		chg9[bp-1] = chg9[pos-1];
		chg9[pos-1] = 9;
		unsigned int it = array2uint(chg9);

		if(NotInResQueue(it))
			AddNewResNode(currState, it);
	}
	//down
	pos = bp+3;
	if((pos>0) && (pos<10))
	{
		unsigned int chg9[9];
		for(int j=0; j<9; ++j) chg9[j] = dgt9[j];
		chg9[bp-1] = chg9[pos-1];
		chg9[pos-1] = 9;
		unsigned int it = array2uint(chg9);

		if(NotInResQueue(it))
			AddNewResNode(currState, it);
	}
	//left
	pos = bp-1;
	if((pos>0) && (pos<10) && ((pos-1)/3 == (bp-1)/3))
	{
		unsigned int chg9[9];
		for(int j=0; j<9; ++j) chg9[j] = dgt9[j];
		chg9[bp-1] = chg9[pos-1];
		chg9[pos-1] = 9;
		unsigned int it = array2uint(chg9);

		if(NotInResQueue(it))
			AddNewResNode(currState, it);
	}
	//right
	pos = bp+1;
	if((pos>0) && (pos<10) && ((pos-1)/3 == (bp-1)/3))
	{
		unsigned int chg9[9];
		for(int j=0; j<9; ++j) chg9[j] = dgt9[j];
		chg9[bp-1] = chg9[pos-1];
		chg9[pos-1] = 9;
		unsigned int it = array2uint(chg9);

		if(NotInResQueue(it))
			AddNewResNode(currState, it);
	}
}

void GenPath(stateNode *currState)
{
	cout<<"\tthe shortest path is found in "<<finishtime-begintime<<"ms"<<endl;
	myPath = new stateNode();
	*myPath = *currState;
	myPath->pNext = NULL;
	currState = currState->pPrev;
	while(currState != NULL)
	{
		++totalSteps;
		stateNode *newNode = new stateNode();
		*newNode = *currState;
		newNode->pNext = myPath;
		myPath = newNode;
		currState = currState->pPrev;
	}
	stateNode *tmp;
	while(myPath)
	{
//		PrintArray(myPath->state);
		tmp = myPath;
		myPath = tmp->pNext;
		delete tmp;
	}
}

void GenResPath(stateNode *currState)
{
	currState = currState->pPrev;
	while(currState != NULL)
	{
		++totalSteps;
//		PrintArray(currState->state);
		currState = currState->pPrev;
	}
	cout<<"\tthere are "<<totalSteps<<" steps in this path."<<endl;
}

bool Meet(stateNode *cs, stateNode *ns)
{
	stateNode *mq = myQueue;
	stateNode *rq = resQueue;
	while(mq != NULL)
	{
		if(mq->state == ns->state)
		{
			finishtime = clock();
			GenPath(mq);
			GenResPath(ns);
			return true;
		}
		mq = mq->pNext;
	}
	while(rq != NULL)
	{
		if(rq->state == cs->state)
		{
			finishtime = clock();
			GenPath(rq);
			GenResPath(cs);
			return true;
		}
		rq = rq->pNext;
	}
	return false;
}

void CalcPath()
{
	begintime = clock();
	stateNode *currState = myQueue;
	stateNode *nowState = resQueue;
	while(!Meet(currState, nowState))
	{
		AddQueue(currState);
		currState = currState->pNext;
		AddResQueue(nowState);
		nowState = nowState->pNext;
	}
}

void DelQueue()
{
	stateNode *tmp = myQueue;
	while(myQueue)
	{
		tmp = myQueue;
		myQueue = tmp->pNext;
		delete tmp;
	}
	tmp = resQueue;
	while(resQueue)
	{
		tmp = resQueue;
		resQueue = tmp->pNext;
		delete tmp;
	}
}

int main()
{
	//sample input and output description
	Description();
	while(true)
	{
		//get input and check whether the path exsits
		if(	GetInput() )
			CalcPath();//calc the path
		else cout<<"\tno path exsits for this start state!"<<endl;
		DelQueue();
		totalSteps = 0;
	}
	return 0;
}